package example2;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

//128. 最长连续序列
public class LeetCode128 {
    public static void main(String[] args) {
//        int[] arr = {4,1,3,2,7,5,6,9,8};
//        new Solution().heapSort(arr);
//        System.out.println(Arrays.toString(arr));
        int[] arr2 = {0,3,7,2,5,8,4,6,0,1};
//        new Solution().heapSort(arr2);
//        System.out.println(Arrays.toString(arr2));
        System.out.println(new Solution128_2().longestConsecutive(arr2));
    }
}

/**
 * 方法二：hash表
 */
class Solution128_2 {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        int max = 0;
        for(Integer num : set){
            if(!set.contains(num - 1)){
                int current = num;
                int sum = 1;
                while(set.contains(current + 1)){
                    current += 1;
                    sum += 1;
                }
                if(sum > max)   max = sum;
            }
        }
        return max;
    }
}

/**
 * 方法一：先排序再计算
 */
class Solution128_1 {
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0)    return 0;
        heapSort(nums);
        int sum = 1;
        int max = 0;
        for(int i=1;i<nums.length;i++){
            if(nums[i] == nums[i-1] + 1){
                sum++;
            }else if(nums[i] > nums[i-1] + 1){
                if(sum > max){
                    max = sum;
                }
                sum = 1;
            }
        }
        if(sum > max){
            max = sum;
        }
        return max;
    }

    //堆排序
    public void heapSort(int[] arr){
        if(arr == null || arr.length == 0)  return;
        int n = arr.length;
        for(int i=n/2-1;i>=0;i--){
            heapify(arr,n,i);
        }
        for(int i=n-1;i>0;i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr,i,0);
        }
    }

    //调整堆中的i节点
    public void heapify(int[] arr,int n,int i){
        if(arr == null || arr.length == 0)  return;
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if(left < n && arr[left] > arr[largest]){
            largest = left;
        }
        if(right < n && arr[right] > arr[largest]){
            largest = right;
        }
        if(i != largest){
            int temp = arr[largest];
            arr[largest] = arr[i];
            arr[i] = temp;
            heapify(arr,n,largest);
        }
    }
}
